package com.suanfa.node;

public class CycleNode {

    public static boolean hasCycle(ListNode head) {

        ListNode p1= head;
        ListNode p2 = head;

        while(p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2 && p1 != head){
                return true;
            }
        }
        return false;
    }

    /**
     * 环形链表长度 找到相遇点之后再次相遇就是环形长度
     */
    public static int cycleLength(ListNode head){
        int length = 0;

        ListNode p1 = head;

        ListNode p2 = head;

        boolean startCount = false;

        while(p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;

            if(p1 == p2 && p1 != head){
                if(startCount){//第二次相遇跳出
                    break;
                }
                startCount= true;
            }
            if(startCount){
                length ++;
            }
        }

        return  length;
    }

    /**
     * 环形链表入口  相交之后， 重新在起点走一次，相交点即为入口
     */
    public static ListNode cycleEnterNode(ListNode head){
        ListNode p1= head;
        ListNode p2 = head;

        while(p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2 && p1 != head){
               break;
            }
        }
        if(p1!= head){
            ListNode p3 = head;
            while(p1!= null){
                p1 = p1.next;
                p3 = p3.next;
                if(p1 == p3){
                   return p1;
                }
            }

        }
        return  null;
    }

}
